class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)# 为什么要+1
        dp[1] = 1
        dp[2] = 1

        代码
        测试用例
        测试用例
        测试结果
        96.
        不同的二叉搜索树
        for i in range(3, n + 1):
            for j in range(1, i//2+1):# 可优化: i//2
                # i-j 不可拆: (i-j)*j
                # i-j 可拆: dp[i - j]*j
                dp[i] = max(dp[i], dp[i - j]*j, (i-j)*j)
        return dp[n]

print(Solution().integerBreak(3))
